/*
 * com.future CO.,ltd.
 */
package com.future;

/**
 * Description:
 * 将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
 * <p>
 * 对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
 * <p>
 * 特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/4/1:23:56
 */
public class Solution_426 {

    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        root.right = new Node(8);
        root.right.left = new Node(6);
        root.right.right = new Node(9);
        Node ans = treeToDoublyList(root);
        System.out.println(ans);
    }

    public static Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        Info allInfo = process(root);
        allInfo.endNode.right = allInfo.firstNode;
        allInfo.firstNode.left = allInfo.endNode;
        return allInfo.firstNode;
    }

    /**
     * ----------------5
     * --------------/  \
     * ------------2     8
     * ----------/ \    / \
     * --------1    3  6   9
     * 当 x = 5
     * 则 lInfo = 1-2-3,firstNode=obj(1),endNode=obj(3)
     * 则 rInfo = 6-8-9,firstNode=obj(6),endNode=obj(9)
     * lInfo.riht=x
     * ==>1-2-3-4-5
     * rInfo.left=x
     * ==>5-6-8-9
     * 所以整体链表：1-2-3-4-5-6-8-9-( 1-2 )
     *
     * @param curNode
     * @return
     */
    private static Info process(Node curNode) {
        if (curNode == null) {
            return new Info(null, null);
        }
        // 获取左侧二叉树的头尾节点
        Info lInfo = process(curNode.left);
        // 获取右侧二叉树的头尾节点
        Info rInfo = process(curNode.right);
        if (lInfo.endNode != null) {
            // 左边链表的尾结点的右节点拼接当前节点
            lInfo.endNode.right = curNode;
        }
        // 当前节点的左节点拼接左边链表的尾结点
        curNode.left = lInfo.endNode;
        // 当前节点的右节点拼接右边链表的头结点
        curNode.right = rInfo.firstNode;
        if (rInfo.firstNode != null) {
            // 右边链表的头结点的左节点拼接当前节点
            rInfo.firstNode.left = curNode;
        }
        // 构建新的当前节点返回
        Info ans = new Info(lInfo.firstNode != null ? lInfo.firstNode : curNode, rInfo.endNode != null ? rInfo.endNode : curNode);
        return ans;
    }

    private static class Info {
        public Node firstNode;
        public Node endNode;

        public Info(Node firstNode, Node endNode) {
            this.firstNode = firstNode;
            this.endNode = endNode;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "firstNode=" + firstNode.val +
                    ", endNode=" + endNode.val +
                    '}';
        }
    }

    /////////////////////////////////////////////一下代码不用提交
    private static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", left=" + left.val +
                    ", right=" + right.val +
                    '}';
        }
    }
}
